package practice;

/**
 * 给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​
 * <p>
 * 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
 * <p>
 * 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 * 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
 * 示例:
 * <p>
 * 输入: [1,2,3,0,2]
 * 输出: 3
 * 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
 */
public class _309_StockWithCooldown {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 0, 2};
        System.out.println(new _309_StockWithCooldown().maxProfit(nums));
    }

    /**
     * 动态规划题
     * <p>
     * 定义：
     * buy[i]为第i天为买的最大收益
     * sell[i]为第i天为卖的最大收益
     * cooldown[i]为第i天为冷冻期的最大收益
     * <p>
     * 递推式：
     * buy[i] = max(buy[i-1], cooldown[i-1] - prices[i]);第i天前最后操作为买，之前没有持有股票或处于冷冻期，最大收益为i-1天买与i-1天为冷冻期的最大值
     * sell[i] = max(buy[i-1] + prices[i],sell[i-1]);第i天前最后操作为卖，之前已经持有，最大收益为i-1天买与i-1天卖的最大值
     * cooldown[i] = sell[i-1];第i天为冷冻期，前一天进行卖出，收益与前一天是一样的
     * ==>简化：
     * buy[i] = max(buy[i-1], sell[i-2] - prices[i])
     * sell[i] = max(buy[i-1] + prices[i], sell[i-1])
     * 初始化：
     * buy[0] = -prices[0]
     * sell[0]=0
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        if (prices.length <= 1) {
            return 0;
        }
        int buy = -prices[0], sell = 0, preBuy=buy, preSell=0;
        for (int i = 1; i < prices.length; i++) {
            preBuy = buy;
            //此时preSell为i-2的sell
            buy = Math.max(preBuy, preSell - prices[i]);
            //此时为i-1的sell
            preSell = sell;
            sell = Math.max(preBuy + prices[i], preSell);
        }
        //最后利益最大的操作肯定为sell
        return sell;
    }
}
